/**
 组合总和II --只能使用一次，不限制层数
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 **一次** 。
注意：解集不能包含重复的组合。 
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:[[1,1,6],[1,2,5],[1,7],[2,6]]
 */
/**
 * [10,1,2,7,6,1,5] 有两个1 会导致有重复的组合，如何解决？
 * 【去重集合】used记录的是同一枝（纵向）的使用情况
 *! 去除重复组合 需要在横向去重
 * candidates[i]==candidates[i-1]
 * !1.used[i-1]=false 同层重复需要去除  false表示之前的元素已经递归回来了， 保证处理的是所有重复元素的第一项
 * 2.used[i-1]=true 同分枝重复不用管--题目中的重复数组每个元素都可以选取
 */
var combinationSum2 = function(candidates, target) {
  const result = [];
  const path = [];
  const used = Array(candidates.length).fill(false)
  candidates.sort((a,b) => a-b);

  const backTracking = (sum, index, used) => {
    if(sum == target) {
      result.push(path.slice());
      return;
    }
    for(let i=index; i<candidates.length; i++) {
      const n = candidates[i];
      if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false) continue;
      if(sum+n > target) break;
      path.push(n);
      used[i] = true;
      backTracking(sum+n, i+1, used);
      path.pop();
      used[i] = false;
    }
  }
  backTracking(0, 0, used);
  return result;
};
const candidates = [10,1,2,7,6,1,5], target = 8;
console.log('组合总和II', combinationSum2(candidates, target));